package com.zjsru.leetcode75.level1;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Author: cookLee
 * @Date: 2023-12-03
 * 无重叠区间
 */
public class EraseOverlapIntervals {

    /**
     * 主
     * \
     * 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
     * 输出: 1
     * 解释: 移除 [1,3] 后，剩下的区间没有重叠。
     * \
     * 输入: intervals = [ [1,2], [1,2], [1,2] ]
     * 输出: 2
     * 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
     * \
     * 输入: intervals = [ [1,2], [2,3] ]
     * 输出: 0
     * 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        EraseOverlapIntervals eraseOverlapIntervals = new EraseOverlapIntervals();
        int[][] intervals = new int[][]{{1,2},{2,3},{3,4},{1,3}};
        System.out.println(eraseOverlapIntervals.eraseOverlapIntervals(intervals));
    }
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length == 0){
            return 0;
        }
        //排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        int len = intervals.length;
        int right = intervals[0][1];
        int ans = 1;
        for (int i = 1; i < len; i++) {
            //左区间比当前右区间大的时候
            if(intervals[i][0] >= right){
                ++ans;
                //更新右区间的最小值
                right = intervals[i][1];
            }
        }
        return len - ans;
    }
}
